package com.jake.data_structure_learning;


import java.util.ArrayList;
import java.util.List;

/**
 * copyright (C), 2021, 北京同创永益科技发展有限公司
 *
 * @author WangXiang
 * @version 1.0.0
 * @create 2021/4/30 10:53
 * @description <author>                <time>                  <version>
 * WangXiang               2021/4/30 10:53            1.0.0
 */
public class Test1 {
    /**
     * 前序遍历  根在前
     */

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        this.preHelper(root, result);
        return result;
    }

    public void preHelper(TreeNode node, List<Integer> result) {
        if(node == null){
            return;
        }

        result.add(node.val);
        if(node.left!=null){
            this.preHelper(node.left,result);
        }

        if(node.right!=null){
            this.preHelper(node.right,result);
        }
    }


    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        this.levelHelper(root,result,0);
        return result;
    }

    public void levelHelper(TreeNode node,List<List<Integer>> result,int level){
        if(node == null){
            return;
        }
        if(level == result.size()){
            result.add(level,new ArrayList<>());
        }

        result.get(level).add(node.val);

        this.levelHelper(node.left,result,level+1);
        this.levelHelper(node.right,result,level+1);
    }

    /**
     * 树对象
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
